/*************************************************************************
 * File Name:    Flatten_Binary_Tree_to_Linked_List.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/11/4 10:11:53
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem: Flatten Binary Tree to Linked List
 | Given a binary tree, flatten it to a linked list in-place.
 |
 | For example,
 | Given
 |
 |      1
 |     / \
 |    2   5
 |   / \   \
 |  3   4   6
 | The flattened tree should look like:
 | 1
 |  \
 |   2
 |    \
 |     3
 |      \
 |       4
 |        \
 |         5
 |          \
 |           6
 | click to show hints.
 |
 | Hints:
 | If you notice carefully in the flattened tree, each node's right child points to
 | the next node of a pre-order traversal.
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode *root)
    {
        if (root == NULL) return;
        TreeNode *cur, *leaf;
        
        cur = root;
        do {
            while (cur != NULL && cur->left == NULL) {
                cur = cur->right;
            }
            if (cur == NULL) return;
            
            leaf = cur->left;
            while (leaf->right != NULL) {
                leaf = leaf->right;
            }
            leaf->right = cur->right;
            cur->right = cur->left;
            cur->left = NULL;
        } while (cur != NULL);
    }

    /* 
     * This is another solution, which I think satisfy the problem's statement.
     * But it is not a pre-order traversal, which can't get Accepted.
     */
    void flatten1(TreeNode *root)
    {
        if (root == NULL) return;
        
        TreeNode *cur, *leaf;
        
        cur = leaf = root;
        
        do {
            while (leaf->right != NULL) {
                leaf = leaf->right;
            }
            while (cur != leaf && cur->left == NULL) {
                cur = cur->right;
            }
            leaf->right = cur->left;
            cur->left = NULL;
            cur = cur->right;
        } while (cur != NULL);
    }
};

